/*
 * 
 */
package edu.gmu.javalution.pfronts;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *
 * @author jason.handuber
 * @deprecated try using {@link DebParetoFronts} if/until I finish implementing
 * this
 */
public class IterativeParetoFronts<VEC, VEC_COMPARER extends Comparator<VEC>>
        implements IParetoFront<VEC>
{

    private final int maxNumberOfFrontsPlusOne;
    private final VEC_COMPARER comparer;
    private final List<ParetoFront<VEC, VEC_COMPARER>> paretoFronts =
                                                       new ArrayList<ParetoFront<VEC, VEC_COMPARER>>();
    private final Set<VEC> displacedBackward = new HashSet<VEC>();

    public IterativeParetoFronts(VEC_COMPARER comparer)
    {
        this(comparer, Integer.MAX_VALUE - 1);
    }

    public IterativeParetoFronts(VEC_COMPARER comparer, int maxNumberOfFronts)
    {
        if (maxNumberOfFronts == Integer.MAX_VALUE)
        {
            //to avoid arithmetic overflow for maxNumberOfFrontsPlusOne
            maxNumberOfFronts = Integer.MAX_VALUE - 1;
        }

        this.comparer = comparer;
        this.maxNumberOfFrontsPlusOne = maxNumberOfFronts + 1;

        if (maxNumberOfFronts <= 0)
        {
            throw new IllegalArgumentException("Must have a positive number " +
                    "of pareto fronts allowed, found: " + maxNumberOfFronts);
        }
    }

    @Override
    public int getNumberOfFronts()
    {
        return paretoFronts.size();
    }

    @Override
    public Collection<VEC> getFront(int index)
    {
        return paretoFronts.get(index).getVectors();
    }

    @Override
    public void add(VEC vector)
    {
        int insertHere = indexedBinarySearch(paretoFronts, vector);

        if (insertHere >= 0)
        {
            final ParetoFront<VEC, VEC_COMPARER> curFront = paretoFronts.get(
                    insertHere);
            curFront.add(vector, displacedBackward);
            if (!displacedBackward.isEmpty())
            {
                //these displaced individuals, unfortunetely, may need to
                //be inserted into the next front, or create their own new
                //front, or some combination. So, TODO: I need to replace the
                //above if with a while !displacedBackwards.isEmtpy(), and
                //I probably need a displacedForwards piece of logic, although
                //I'm not completely sure about that one.
                final ParetoFront<VEC, VEC_COMPARER> newFront =
                                                     new ParetoFront<VEC, VEC_COMPARER>(
                        comparer, displacedBackward);
                paretoFronts.add(insertHere + 1, newFront);
                displacedBackward.clear();
            }
        }
        //this means that this new vector doesn't belong in any currently
        //existing front, so we'll place it in a new front and insert that
        //front at the index at which it belongs
        else
        {
            final ParetoFront<VEC, VEC_COMPARER> newFront =
                                                 new ParetoFront<VEC, VEC_COMPARER>(
                    comparer, vector);
            final int insertionIndex = -1 * insertHere - 1;
            paretoFronts.add(insertionIndex, newFront);
        }

        if (paretoFronts.size() == maxNumberOfFrontsPlusOne)
        {
            paretoFronts.remove(paretoFronts.size() - 1);
        }
        assert (paretoFronts.size() <= maxNumberOfFrontsPlusOne) :
                "Number Fronts; " + paretoFronts.size() +
                " but max num fronts = " + maxNumberOfFrontsPlusOne;
    }

    @Override
    public String toString()
    {
        String s = "";
        int frontIndex = 0;
        for (ParetoFront<VEC, VEC_COMPARER> front : paretoFronts)
        {
            s += (frontIndex++) + "] => [" + front.toString() + "]\n";
        }
        return s;
    }

    private final static <VEC, VEC_COMPARER extends Comparator<VEC>> int indexedBinarySearch(
            final List<ParetoFront<VEC, VEC_COMPARER>> l,
            final VEC key)
    {
        int low = 0;
        int high = l.size() - 1;

        while (low <= high)
        {
            int mid = (low + high) >>> 1;
            ParetoFront<VEC, VEC_COMPARER> midVal = l.get(mid);
            //TODO: Since I know that midVal is -1, 0, or 1, use a switch
            //statement, also capture the trail back part of this special
            //modified search with the -42 key value
            //cmp: -1 if key < midVal, 0 if within, +1 if key > midVal
            int cmp = midVal.compareParetoTo(key);

            if (cmp < 0)
            {
                low = mid + 1;
            }
            else if (cmp > 0)
            {
                high = mid - 1;
            }
            else
            {
                return mid; // key found
            }
        }
        return -(low + 1);  // key not found
    }
}
